package LinkedList;

import Node.ListNode;

public class ReverseNList {

    /**
     * 迭代翻转N个节点的链表
     * @param head 链表头结点
     * @param k 需要翻转的节点个数
     * @return 翻转后的链表头结点
     */
    public ListNode iterationReverseNList(ListNode head, int k) {
        if (head == null || head.next == null)
            return head;
        ListNode cur, pre, next;
        cur = head;
        pre = null;
        next = head.next;
        while (k != 0) {
            cur.next = pre;
            pre = cur;
            cur = next;
            if (next != null) {
                next = next.next;
            }
            k--;
        }
        // 此时的cur是第 n + 1 个节点，head节点是翻转后的尾节点
        head.next = cur;
        // 此时的pre是翻转后的头结点
        return pre;

    }

    // 后驱节点
    private ListNode successor = null;

    /**
     * 递归翻转N个节点的链表
     * @param head 链表头结点
     * @param k 需要翻转的节点个数
     * @return 翻转后的链表头结点
     */
    public ListNode recursiveReverseNList(ListNode head, int k) {
        if (k == 1) {
            // 记录第 n + 1 个节点
            successor = head.next;
            return head;
        }

        // 以head.next为起点，需要翻转的节点个数减一，返回新的头结点
        ListNode last = recursiveReverseNList(head.next, k - 1);
        head.next.next = head;
        head.next = successor;
        return last;

    }
}
